package example;

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 * @author 颜培轩
 * @date date
 */
public class exam {

    public static void main(String args[]) {
        // 测试题 1
        int[] a = {0, 0, 3, 2, -1, 4};
        int[] ints = exam1(a);
        System.out.println("ints = " + Arrays.toString(ints));

        //测试题 2
        String s = exam2(14331);
        System.out.println("s = " + s);
    }

    /**************************************** exam1  start  ************************************************************/
    /**
     * 给定一个由正数,负数和0组成的整数数组,将所有为0的元素,挪到数组末尾。要求时间复杂度O(n)
     * 请设计一个函数,完成此功能。
     */
    public static int[] exam1(int[] a) {
        int length = a.length;
        int point = 0; // 不为0 的位置
        int result[] = new int[length];

        for (int i = 0; i < length; i++) {
            if (0 != a[i]) {
                result[point++] = a[i];
            }
        }
        while (point < length) {
            result[point++] = 0;
        }
        return result;
    }
    /**************************************** exam1  end ************************************************************/


    /**************************************** exam2  start ************************************************************/
    /**
     * 给定任意一个自然数，获取它重新排列后，下一个比它大的自然数，要求时间复杂度O(n)。例如：
     * 给定1233,它的下一个是1323；
     * 给定1323,它的下一个是1332；
     * 给定9876,它的下一个不存在；
     * 请设计一个函数，完成此功能。(语言不限)
     */
    public static String exam2(int a) {
        ArrayList<Integer> nums = new ArrayList<>();
        //拆分自然数，放入数组
        while ((a % 10) > 0) {
            int t = a % 10;
            a = a / 10;
            nums.add(0, t);
        }

        // 寻找要交换的位置
        int point = findPoint(nums);

        if (point == -1) {
            return "不存在";
        }

        //point 的前一位位置 与 后面值交换
        int left = nums.get(point - 1);
        for (int i = nums.size() - 1; i >= point; i--) {
            int right = nums.get(i);
            if (right > left) {
                nums.set(point - 1, right);
                nums.set(i, left);
                break;
            }
        }

        for (int i = point, j = nums.size() - 1; i < j; i++, j--) {
            int t = nums.get(j);
            nums.set(j, nums.get(i));
            nums.set(i, t);
        }
        return nums.toString();
    }

    public static int findPoint(ArrayList<Integer> nums) {
        for (int i = nums.size() - 1; i > 0; i--) {
            if (nums.get(i) > nums.get(i - 1)) {
                return i;
            }
        }
        return -1;
    }

    /**************************************** exam2  end ************************************************************/
}
